As a hardware-directed algorithm for an elementary function operation, such as a trigonometric function, a CORDIC (COordinate Rotation Digital Computer) algorithm is known. The CORDIC is an iterative computing algorithm and expresses functions as vector rotation on a two-dimensional plane, and finds a true value by iterative vector rotation of a predetermined basic rotational angle. In the CORDIC algorithm, by selecting a rotational coordinate system (linear, circular, or hyperbolic), and by repeating a simple operation of a shift, addition, subtraction and table look-up, multiplication and division, trigonometric function computations, exponential and logarithmic computations, and hyperbolic function computations and the like can be executed. The CORDIC algorithm is widely used in digital signal processing fields.
The shift addition-and-subtraction means a operation composed of shift operations and an addition-and-subtraction.
Hereinafter, the CORDIC algorithm will be described in detail.
a j-th rotation process is represented by Equation (1).
                                                                                                              x                    ⁡                                          (                                              j                        +                        1                                            )                                                        =                                                            x                      ⁡                                              (                        j                        )                                                              +                                          m                      ⁢                                                                                          ⁢                                              σ                        j                                            ⁢                                              2                                                  -                          j                                                                    ⁢                                              y                        ⁡                                                  (                          j                          )                                                                                                                                                                                                              y                    ⁡                                          (                                              j                        +                        1                                            )                                                        =                                                            y                      ⁡                                              (                        j                        )                                                              -                                                                  σ                        j                                            ⁢                                              2                                                  -                          j                                                                    ⁢                                              x                        ⁡                                                  (                          j                          )                                                                                                                                                                                                              z                    ⁡                                          (                                              j                        +                        1                                            )                                                        =                                                            z                      ⁡                                              (                        j                        )                                                              +                                                                  σ                        j                                            ⁢                                              α                        j                                                                                                                          }                ⁢                                  ⁢                              α            j                    =                                    1                              m                                      ⁢                          arctan              ⁡                              (                                                      m                                    *                                      2                                          -                      j                                                                      )                                                    ⁢                                  ⁢                              j            =            0                    ,          1          ,          …          ⁢                                          ,                      n            -            1                          ⁢                                  ⁢                  m          =                      {                                                            1                                                                      (                                          Circular                      ⁢                                                                                                                        ⁢                                                                                                                      ⁢                      coordinate                      ⁢                                                                                          ⁢                      system                                        )                                                                                                0                                                                      (                                                                  Linia                        ⁢                        r                                            ⁢                                                                                          ⁢                      coodinate                      ⁢                                                                                          ⁢                      system                                        )                                                                                                                    -                    1                                                                                        (                                          Hyperbolic                      ⁢                                                                                          ⁢                      oodinate                      ⁢                                                                                          ⁢                      system                                        )                                                                                                          (        1        )            
Here, n is an iteration count, and αj is an angle of a micro-rotation. And σjε{1,−1} is a parameter on a rotation direction (hereinafter, denoted as rotation direction parameter).
Taking circular polar coordinates as an example, A vector [x(n), y(n)]′ implementing a rotation of a rotational angle θ with respect to a vector [x(0), y(0)]′ is represented by Equation (2) and Equation (3) based on Equation (1).
                              [                                                                      x                  ⁡                                      (                    n                    )                                                                                                                        y                  ⁡                                      (                    n                    )                                                                                ]                =                                            1                              K                n                                      ⁡                          [                                                                                          cos                      ⁢                                                                                          ⁢                      θ                                                                                                  sin                      ⁢                                                                                          ⁢                      θ                                                                                                                                                          -                        sin                                            ⁢                                                                                          ⁢                      θ                                                                                                  cos                      ⁢                                                                                          ⁢                      θ                                                                                  ]                                ⁡                      [                                                                                x                    ⁡                                          (                      0                      )                                                                                                                                        y                    ⁡                                          (                      0                      )                                                                                            ]                                              (        2        )                                          K          n                =                  1          /                                    ∏                              j                =                0                                            n                -                1                                      ⁢                                                  ⁢                                          1                +                                  2                                                            -                      2                                        ⁢                    j                                                                                                          (        3        )            
Here, Kn is a scaling factor. The rotation based on the CORDIC algorithm is a pseudo rotation that accompanies scaling. In order to correct the scaling, it is necessary to perform processing indicated in Equation (4).
                              [                                                    xf                                                                    yf                                              ]                =                              K            n                    ⁡                      [                                                                                x                    ⁡                                          (                      n                      )                                                                                                                                        y                    ⁡                                          (                      n                      )                                                                                            ]                                              (        4        )            
As indicated in Equation (5), the CORDIC algorithm realizes a rotation operation of the rotational angle θ as a combination of basic rotation of angle αj.
                    θ        =                              ∑                          j              =              0                                      n              -              1                                ⁢                                          ⁢                                    σ              j                        ⁢                          α              j                                                          (        5        )            
The CORDIC algorithm has 2 modes: a Rotation mode and a Vector mode, according to a method of determining the rotation direction parameter σj given in Equation (6).
                              σ          j                =                  {                                                                                          sign                    ⁡                                          (                                              z                        ⁡                                                  (                          j                          )                                                                    )                                                        ⁢                                                                          ⁢                                      (                    Rotation                    )                                                                                                                                            sign                    ⁡                                          (                                              y                        ⁡                                                  (                          j                          )                                                                    )                                                        ⁢                                                                          ⁢                                      (                    Vectoring                    )                                                                                                          (        6        )            
In the Rotation mode, with a desired angle θ as z(0), processing is performed to rotate, by an amount θ, an initial vector [x(0), y(0)]′. In the Vector mode, with an initial angle z(0) as 0, a process is performed to rotate the vector up to an x axis, and to obtain a rotational angle (z(n)) thereof and the norm (x(n)) of the initial vector.
Since the CORDIC algorithm implements the rotation process by n basic rotations, essentially a rotational angle error less than a final basic rotational angle αn−1 occurs. Equation (7) holds true with n bit accuracy. The CORDIC algorithm has to perform iterative processing of the same number of stages as the required bit accuracy.α≅2−j(j>n/3)  (7)
As mentioned above, the CORDIC algorithm is a unified algorithm operating multiplication and division, trigonometric function, exponential and logarithmic functions, hyperbolic function and the like. As a processor for digital signal processing taking advantages of the feature, a first related art which adopts a CORDIC circuit as a basic processing element is known (refer to the non-patent literature 1 and the non-patent literature 2).
FIG. 7 shows a diagram showing a configuration of processor shown in the first related art, processor 1000 includes control circuit 1001, M CORDIC-Processing Elements (hereinafter, referred to as CORDIC-PE) 10021 to 1002M and memory 1003. The M is a positive integer.
a memory 1003 reads out data (input data) for the input of CORDIC-PEs 10021 to 1002M according to an address that control circuit 1001 provides, and writes from CORDIC-PEs 10021 to 1002M's output data (operation result)
CORDIC-PEs 10021 to 1002M change the operational mode based on an operational mode control signal from control circuit 1001. CORDIC-PEs 10021 to 1002M operate the input data from the memory 1003 and returns the result to memory 1003. The operational mode defines a kind of operations, including multiplication and division, trigonometric function, exponential and logarithmic functions, hyperbolic function or the like in the CORDIC algorithm.
DFT (Discrete Fourier Transform) is one of the commonly used operation in the field of digital signal processing. N-point DFT processing N-point discrete periodic data is expressed in Equation (8).
                                                        X              ⁡                              (                k                )                                      =                                          ∑                                  n                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                x                  ⁡                                      (                    n                    )                                                  ⁢                                  W                  N                  kn                                                              ,                                          ⁢                      k            =            0                    ,          1          ,          …          ⁢                                          ,                      N            -            1                          ⁢                                  ⁢        where        ⁢                                  ⁢                  W          =                      ⅇ                                          -                j                            ⁢                                                2                  ⁢                  π                                N                                                                        (        8        )            
Here, N is assumed to be N1*N2 (“*” means multiplication in following equations), and then Equation (8) is rewritten by Equation (9).
                                          X            ⁡                          (                                                k                  1                                +                                                      N                    1                                    ⁢                                      k                    2                                                              )                                =                                    ∑                                                n                  2                                =                0                                                              N                  2                                -                1                                      ⁢                                                  ⁢                                          (                                                      ∑                                                                  n                        1                                            =                      0                                                                                      N                        1                                            -                      1                                                        ⁢                                                                          ⁢                                                            x                      ⁡                                              (                                                                                                            N                              2                                                        ⁢                                                          n                              1                                                                                +                                                      n                            2                                                                          )                                                              ⁢                                          W                                              N                        1                                                                                              k                          1                                                ⁢                                                  n                          2                                                                                                                    )                            ⁢                              W                N                                                      k                    1                                    ⁢                                      n                    2                                                              ⁢                              W                                  N                  2                                                                      k                    2                                    ⁢                                      n                    2                                                                                      ⁢                                  ⁢                              n            =                                                            N                  2                                ⁢                                  n                  1                                            +                              n                2                                              ,                      k            =                                          k                1                            +                                                N                  1                                ⁢                                  k                  2                                                                    ⁢                                  ⁢        where        ⁢                                  ⁢                              0            ≤                          n              1                        ≤                          N              1                                ,                      0            ≤                          n              2                        ≤                          N              2                                ,                      0            ≤                          k              1                        ≤                          N              1                                ,                      0            ≤                          k              2                        ≤                          N              2                                                          (        9        )            
According to Equation (9), N-point DFT carries out N2-point DFT N1 times after multiplying the twiddle factor WNk1n2 with a result of carrying out N1-point DFT N2 times.
In a similar way, when
      N    =                  ∏                  i          =          0                          S          -          1                    ⁢                          ⁢              R        i              ,N-point DFT is processed through S stages. At each stage, (N/Ri) Ri-point DFTs (“/” means division in following equations), and multiplication of the twiddle factor (twiddle factor multiplication) are carried out. The stage is defined as one step when the operation process is divided into a plurality of steps. R-point DFT at each stage is called a R-radix butterfly operation. The small-N algorithm is an example for realizing the butterfly operation (for example, refer to the non-patent literature 3).
Hereinafter, the radix-2, radix-4, and radix-5 butterfly operations with the small-N algorithm will be described with reference to FIGS. 8 to 10.
As shown in Equation (8) and Equation (9), power-of-2 Point-DFT can be decomposed into the radix-2 butterfly operations shown in FIG. 8, and the twiddle factor multiplications. The twiddle factor multiplication is carried out in the circular coordinate system Rotation mode of CORDIC. As shown in Equation (10), the radix-2 butterfly operation are divided into the π/4 rotation process and the scaling process of multiplying ±√{square root over (2)}.
                              [                                                                      X                  ⁡                                      (                    0                    )                                                                                                                        X                  ⁡                                      (                    1                    )                                                                                ]                =                                            [                                                                    1                                                        1                                                                                        1                                                                              -                      1                                                                                  ]                        ⁡                          [                                                                                          x                      ⁡                                              (                        0                        )                                                                                                                                                        x                      ⁡                                              (                        1                        )                                                                                                        ]                                =                                                    [                                                                                                    2                                                                                    0                                                                                                  0                                                                                      -                                                  2                                                                                                                    ]                            ⁡                              [                                                                                                    1                                                  2                                                                                                                                    1                                                  2                                                                                                                                                                        -                                                  1                                                      2                                                                                                                                                              1                                                  2                                                                                                                    ]                                      ⁡                          [                                                                                          x                      ⁡                                              (                        0                        )                                                                                                                                                        x                      ⁡                                              (                        1                        )                                                                                                        ]                                                          (        10        )            
When ignoring the scaling process of multiplying √{square root over (2)}, the π/4 rotation can be processed with Rotation mode of CORDIC in the circular coordinate system. Effect of sign inversion cancels out additional π phase rotation in the twiddle factor multiplication The effect with √{square root over (2)} scaling can be canceled by scaling correction after all stage. The scaling correcting process can be carried out in the multiplication mode (linear coordinate system Rotation mode) of the CORDIC. Accordingly, power-of-2 DFT can be processed with the CORDIC. Details thereof is disclosed in the non-patent literature 1.
As shown in FIG. 9 and FIG. 10, the 3-radix and radix-5 butterfly operations can be carried out by addition-and-subtraction and a coefficient multiplication similarly to radix-2 butterfly operation. The butterfly any-integer radix operation can be processed through the addition-and-subtraction and the coefficient multiplication. The coefficient multiplication can be carried out in the multiplication mode of CORDIC. Therefore, the any-integer radix butterfly operation is possible with only the CORDIC.
The processor of the first related art adopts the CORDIC-PE as a basic operational circuit. In the processor, two input addition-and-subtraction for butterfly operation requires one CORDIC operation involving iterative shift addition-and-subtraction with the same number of steps as the required bit accuracy(n) shown in Equation (1). Therefore, the above-mentioned processor is inefficient. The scaling correcting process involved also increase operation complexity.
As a basic operational circuit in order to solve this problem, processor of a second related art adopts a basic operational circuit which have a butterfly operational circuit in addition to the CORDIC-PE (for example, refer to the non-patent literature 4 and the non-patent literature 5).
FIG. 11 shows a diagram of a processor shown in the second related art. A processor 2000 includes a butterfly operational circuit 2002 and the composition of a processor 1000 adopted by the first related art. The butterfly operational circuit 2002 carries out the butterfly operation whose radix is designated based on a radix changing control signal issued by a control circuit 1001. Here, annotation of symbols in FIG. 11 is the same as FIG. 7.